{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ex1：乘法口诀表\n",
    "\n",
    "<img src=\"../images/ch01/ex4.png\" width=\"480\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mults():\n",
    "    ## your code starts here\n",
    "    for i in range(1,10):\n",
    "        for j in range(1,i+1):\n",
    "            print(i,\"*\",j,\"=\",i*j,end=\"  \")\n",
    "        print()    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 * 1 = 1  \n",
      "2 * 1 = 2  2 * 2 = 4  \n",
      "3 * 1 = 3  3 * 2 = 6  3 * 3 = 9  \n",
      "4 * 1 = 4  4 * 2 = 8  4 * 3 = 12  4 * 4 = 16  \n",
      "5 * 1 = 5  5 * 2 = 10  5 * 3 = 15  5 * 4 = 20  5 * 5 = 25  \n",
      "6 * 1 = 6  6 * 2 = 12  6 * 3 = 18  6 * 4 = 24  6 * 5 = 30  6 * 6 = 36  \n",
      "7 * 1 = 7  7 * 2 = 14  7 * 3 = 21  7 * 4 = 28  7 * 5 = 35  7 * 6 = 42  7 * 7 = 49  \n",
      "8 * 1 = 8  8 * 2 = 16  8 * 3 = 24  8 * 4 = 32  8 * 5 = 40  8 * 6 = 48  8 * 7 = 56  8 * 8 = 64  \n",
      "9 * 1 = 9  9 * 2 = 18  9 * 3 = 27  9 * 4 = 36  9 * 5 = 45  9 * 6 = 54  9 * 7 = 63  9 * 8 = 72  9 * 9 = 81  \n"
     ]
    }
   ],
   "source": [
    "mults()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ex2：洗牌\n",
    "\n",
    "洗牌后的每个元素随机出现在每个位置，且<B><I>概率相同</I></B>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def shuffle_system(cards):\n",
    "    random.shuffle(cards)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shuffle_correct(cards):\n",
    "    ## your code starts here\n",
    "    for i in range(len(cards)):\n",
    "        randi = random.randint(i,len(cards)-1)\n",
    "        cards[i],cards[randi] = cards[randi],cards[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [i for i in range(0, 10)]\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 9, 4, 8, 0, 7, 5, 1, 2, 3]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shuffle_correct(A)\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "shuffle_system(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 4, 9, 8, 7, 5, 3, 6, 2]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_shuffle(f):\n",
    "    result = [[0 for i in range(10)] for j in range(10)]\n",
    "\n",
    "    for i in range(10000):\n",
    "        A = [i for i in range(0, 10)]\n",
    "        f(A)\n",
    "        for j in range(len(A)):\n",
    "            result[A[j]][j] += 1\n",
    "        \n",
    "    print('\\n'.join([''.join(['{:6}'.format(item) for item in row]) \n",
    "          for row in result]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   976  1025  1010  1008   972   976  1017   996  1002  1018\n",
      "   942  1057  1000  1025  1003  1019  1006   980  1007   961\n",
      "  1004  1051  1028  1036   980   983  1013   999   943   963\n",
      "   951  1009  1008   990   989  1024   976   992  1039  1022\n",
      "  1038   987  1017   975  1007  1012   983  1007   982   992\n",
      "  1016   973   968   969  1004  1012   982  1015  1054  1007\n",
      "  1031   952   961  1011  1036   978  1026   972  1032  1001\n",
      "  1001   996   999   997   956  1021   972  1003   995  1060\n",
      "   996   952  1009  1013  1037  1008   999  1042   962   982\n",
      "  1045   998  1000   976  1016   967  1026   994   984   994\n"
     ]
    }
   ],
   "source": [
    "test_shuffle(shuffle_correct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1000  1029   993  1016  1018   992   977   963  1001  1011\n",
      "   986   979  1084  1029   990   957   981   961  1000  1033\n",
      "  1027  1012   977   992   979  1002   981  1037  1012   981\n",
      "   982   973  1029  1034   945  1001  1020   987   996  1033\n",
      "  1018   967  1033   980  1002  1082   977  1042   958   941\n",
      "  1002  1008   950  1089   975  1022   987   983   992   992\n",
      "   963  1006   975   957  1007   987  1069   983  1051  1002\n",
      "  1055  1008   978   974   996   980   990   975  1007  1037\n",
      "   950  1007   978   949  1060   958  1055  1031  1010  1002\n",
      "  1017  1011  1003   980  1028  1019   963  1038   973   968\n"
     ]
    }
   ],
   "source": [
    "test_shuffle(shuffle_system)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ex3：数质数\n",
    "\n",
    "给定一个正整数n，计算出小于等于n的质数有多少个。\n",
    "比如17，则返回7，因为小于等于7的质数有2，3，5，7，13，17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_prime(n):\n",
    "    ## your code starts here\n",
    "    is_prem = [True]*(n+1)\n",
    "    i = 2\n",
    "    while (i*i<=n):\n",
    "        if is_prem[i]:\n",
    "            j = i\n",
    "            while(i*j<=n):\n",
    "                is_prem[i*j] = False\n",
    "                j+=1\n",
    "        i+=1\n",
    "    count = 0\n",
    "    for i in range(2,n+1):\n",
    "        if is_prem[i]:\n",
    "            count+=1\n",
    "            print(i,end=' ')\n",
    "    return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 "
     ]
    },
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_prime(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ex4：哥德巴赫猜想\n",
    "任一大于2的偶数，都可表示成两个质数之和。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def goldbach(n):\n",
    "    ## your code starts here\n",
    "    is_prem = [True]*(n+1)\n",
    "    i = 2\n",
    "    while(i*i<=n):\n",
    "        j = i\n",
    "        while(j*i<=n):\n",
    "            is_prem[j*i] = False\n",
    "            j+=1\n",
    "        i+=1\n",
    "    primes = []\n",
    "    for i in range(2,n+1):\n",
    "        if is_prem[i]:\n",
    "            primes.append(i)\n",
    "    first = 0\n",
    "    last = len(primes)-1\n",
    "    while(first<last):\n",
    "        if(primes[first]+primes[last]==n):\n",
    "            print(n,\" = \", primes[first], \" + \", primes[last])\n",
    "            first+=1\n",
    "            last-=1\n",
    "        elif (primes[first]+primes[last]>n):\n",
    "            last-=1\n",
    "        else:\n",
    "            first+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100  =  3  +  97\n",
      "100  =  11  +  89\n",
      "100  =  17  +  83\n",
      "100  =  29  +  71\n",
      "100  =  41  +  59\n",
      "100  =  47  +  53\n"
     ]
    }
   ],
   "source": [
    "goldbach(100)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
